In a communications controller to which are connected a plurality of users, the data or messages broadcasts require that the data be duplicated as many times as there are users to which the data or the messages are to be transferred. Two main drawbacks spring from this problem of multicasting.
Firstly, in a data store in which to each user corresponds its own memory space, re-writing a message many times in each memory space for different users affects the performance of the machine because of the writing delays.
Secondly, the storage of the messages in the data store for different users represents a waste of memory space.
Therefore, it is necessary to provide a device and a method which enable improving the performance of multicasting a message by avoiding the execution of useless operations of re-writing and re-deleting the memory space of each user.
In a communications network, the control systems located at the network node have to service more and more users through high speed links. A system provided with the capability of servicing high speed communication links via a high speed adapter is described in the Patent Application EP A 244 544. The system comprises a central control unit running a network control program which assigns buffers of the central control unit memory to the user links. The high speed adapter is provided with buffering means into which the data portion of the received frames are assembled to be stored into the memory of the central control unit through a direct memory access path. The performance of such a system is limited by the fact that the messages have to be managed by the microcode and that the message exchanges require the intervention of the central control unit.
A mechanism for transferring messages between source and destination users through a shared memory has also been disclosed in the European application whose publication number is EP A1 365 731. The invention provides a mechanism, implemented in a communication network node, which enables messages to be exchanged between the adapters connected to the same shared memory and wherein the exchanges do not require any intervention of a costly central control unit. The mechanism is a major improvement in the exchange mechanism. Even though its implementation enables short messages to be exchanged without any risk of over-run, the throughput of the line interface module, in term of megabits per second, is not acceptable when the packet size decreases. This drawback may be avoided by devising an improved line interface module which enables to accessing of the shared memory in a more efficient way.
The line interface module (LIM) architecture in the prior art, refer to FIG. 1-A, is based on a shared memory "data store" (100) that provides a data repository and on a message transfer mechanism to its users. The data store consists of a buffered partition of 4 Megabytes of RAM and a linear partition of RAM. This shared memory is connected to a data store manager DSM (110) which controls the storage in the shared memory and is also an arbiter for the DS bus. The DSM is connected through a Data Store Bus (101) which is 4-byte wide, 40 ns cycle time that gives a 800 Mbps capability, to:
a local store (120) dedicated to a microprocessor, PA1 a microprocessor (130) with its own local store holding instructions and data, this microprocessor may be an Intel 486, PA1 a Device Communication Server (DCS) (140), and PA1 a Data Store Interface (DSI) (150) disclosed in detail in the European Patent Application EP A1 365 731. This DSI is connected to a plurality of interface adapters (IFA) and scanners (152) through a High Performance Parallel Bus (HPPB) (102) which is 2 bytes wide and 60 ns cycle time that gives a 260 Mbps speed. A second DSI is used to interface a Connectivity SubSystem Switch (154) through a specific bus which is at 128 Mbps full duplex. The CSS switch enables interconnection several LIMs. PA1 lease buffer: a 256-byte buffer is removed from a free buffer queue stored in the data store and allocated to a user that has requested this operation. This user can then write the data inside this newly acquired buffer. Only one buffer is removed for this operation. PA1 enqueue message: a set of chained buffers forming a message are put into a queue belonging to the user that has requested this operation. That user can then dispatch the set of chained buffers to process the message. PA1 dequeue message: a message is taken by a user from one of its queues in order to process that message. PA1 release message: a set of chained buffers is moved back into the free buffer queue. PA1 (a) organizing said plurality of control blocks in a plurality of direct control blocks (DCB) wherein each said direct control block is associated to a data buffer the address of which has a predetermined relationship with the address of the corresponding direct control block, PA1 (b) building a free direct control block queue (FDCBQ) which stores the addresses of all the free direct control blocks and chaining said free DCBs, said queue being controlled by a control block (FDQCB) which stores the addresses of the first and the last free direct control blocks respectively in its head (H) field and its tail (T) field, PA1 (c) organizing said plurality of control blocks in a plurality of indirect control blocks (ICB) to enable the multicast function to be performed message by message, PA1 (d) building a free indirect control block queue (FICBQ) which stores the addresses of all the free indirect control blocks and chaining said free indirect control blocks, said queue being controlled by a control block (FIQCB) which stores the addresses of the first and the last free indirect control blocks respectively in its head (H) field and its tail (T) field, PA1 (e) leasing a necessary number of free direct control blocks from said FDCBQ, each free DCB being associated to a free data buffer, in order to store the message received in said data buffers, PA1 (f) storing in said free direct control blocks the information relative to the associated data buffers which constitute the original message, PA1 (g) enqueueing said message in the message queue of a selected user by enqueueing the associated direct control blocks in said user queue, PA1 (h) leasing successively a free indirect control block from the FICBQ to store the information relative to the message to be multicast in each of said ICBs for each multicasting operations, PA1 (i) storing the information relative to the message to be multicast in each one of said free indirect control blocks, each ICB pointing to the direct control block corresponding to the first data buffer of the original message, each one of said ICBs representing a duplicated message, and PA1 (j) enqueueing said indirect control block in the message queue of each user to which the message has to be transmitted, for each one of the multicasting operations. PA1 a plurality of direct control blocks (DCB) wherein each said direct control block is associated to a data buffer the address of which has a predetermined relationship with the address of the corresponding direct control block. PA1 a free direct control block queue (FDCBQ) which stores the addresses of all the free direct control blocks and chaining said free DCBs, said queue being controlled by a control block (FDQCB) which stores the addresses of the first and the last free direct control blocks respectively in its head (H) field and its tail (T) field, PA1 a plurality of indirect control blocks (ICB) to enable the multicast function to be performed message by message, and PA1 a free indirect control block queue (FICBQ) which stores the addresses of all the free indirect control blocks and chaining said free indirect control blocks, said queue being controlled by a control block (FIQCB) which stores the addresses of the first and the last free indirect control blocks respectively in its head (H) field and its tail (T) field.
The DCS comprises a Free Buffer Supplier (FBS) and a Global Order Machine (GOM), not shown in this FIG. 1-A, which centralizes all the global orders also called primitives thru which the users of the shared data store (100) exchange messages. To execute the global orders, the users invoke the GOM via the data store bus. There are four global orders:
In this way, the messages in the shared memory can be transferred between different users without moving the data, but by manipulating the control blocks associated to each buffer or message.
This LIM architecture has been developed with an objective of exchanging data in a flexible way thanks to the organization of the control blocks which are stored as well as the messages in the data store. The mechanism for exchanging data is flexible in the sense that it enables the users to exchange messages by invoking primitives, to define any configurations in terms of priority, number of queues etc. . . .
Therefore, the main drawback of this LIM architecture is that it is tuned for the handling of low-speed and medium-speed communication links (up to T1 speed which is 1.5 Mbits per second) where there is no need to optimize that much the primitive operations. The flexibility has been traded against the efficiency because the bus speed is over-sized when compared to the link speed.
Such a statement becomes no longer valid if the media speed has to reach the rate of T3 (45 Mbits per second) and OC3 which is three times the T3 rates. Indeed, the processing overhead due to the bus arbitration and to the passing of control messages over the DS bus, limits the throughput of the bus. As is shown in FIG. 1-B, this throughput is much dependant on the packet length. It is equal to 400 Mbps for 4 Kbytes packets, and it is reduced to 22 Mbps for 12 bytes packets. Therefore, this limitation precludes the use of the LIM to support any type of traffic around or above the T3 rate with a satisfactory media utilization.
The environment in which the invention may be implemented is described in detail in the patent application EP A1 365 731. Indeed, the present invention requires that the memory space be organized in such a way that it contains at least a buffered space wherein each page of the buffered space is divided in a number of M+1 buffers with M buffers devoted to the storage of data and one control buffer divided into M control blocks. The control blocks are devoted to the storage of buffer and chaining information. Each data buffer has a fixed address relationship with a buffer control block. The conception of the linear space to be associated to the buffered space in the shared memory described in the patent application mentioned above is also required for the present invention but it is not necessary to centralize it in the shared memory as well as the control blocks which can also be accessed separately from the data buffers.